vector<Pieza*> piezasCandidatas(Tablero &t, vector<Pieza> &piezas, int posx, int posy, int &cant)		// O(n_piezas)
{
  vector<Pieza*> candidatos;
    
  for(int i = 0; i < piezas.size(); i++)
  {
    if(t.usadas[i] == 0)
    {
      if(noEsTablero(t, posx-1, posy) || t.posiciones[posx-1][posy]->inf == piezas[i].sup)
      {
        if(noEsTablero(t, posx, posy-1) || t.posiciones[posx][posy-1]->der == piezas[i].izq)
        {
          candidatos.push_back(&piezas[i]);
          cant ++;
         }
      }   
    }
  }
  return candidatos;
}

bool noEsTablero(Tablero &t, int posx, int posy){	// O(1)
	//si estoy fuera de los limites del tablero o es una ficha comodín(NULL)
  if(posx < 0 || posy < 0 || posx >= t.cant_rows || posy >= t.cant_cols || t.posiciones[posx][posy]==NULL){return true;} 
  return false;  
}


bool recursion(Tablero &t, Tablero &t_opt, vector<Pieza> &piezas, int posx, int posy){

  if (posy == t.cant_cols)// Si estoy al final de la fila paso a la proxima
  {
    posx += 1;
    posy =  0;
  }

  //si estoy al final, me fijo:
  if(posx == t.cant_rows)
  {
    if (piezas.size()==t.cant_usadas) // Si se completo devuelvo true y termino
    {
      return true;
    }
    else
    {         
      if(t_opt.cant_usadas < t.cant_usadas) //sino chequeo si cubre mas piezas
      {
      	t_opt=t;
      }
      return false;
    }
  }
 
  
  int posiciones_libres = piezas.size() - ((posx*t.cant_cols) + posy);	//O(1)
  int cantidad_max_posible = t.cant_usadas + posiciones_libres;		//O(1)
  
  if(cantidad_max_posible < t_opt.cant_usadas) //si se que no voy a encontrar una solucion mejor ya no sigo y corto la recursion
  {
    return false;
  }
  
  vector<Pieza*> candidatos;
  int tam = piezas.size();
  candidatos.resize(tam);			//O(n)
  int cant_candidatas = 0; 
  candidatos = piezasCandidatas(t, piezas, posx, posy, cant_candidatas);       //O(n_piezas)
  
  for (int i = 0; i < cant_candidatas; i++)
  { 
    t.posiciones[posx][posy] = candidatos[i];
    t.usadas[candidatos[i]->num] = 1;
    t.cant_usadas += 1;
   
       
    if(recursion(t,t_opt, piezas, posx, posy+1))
    {
      return true;
    } 
     
    /*si no, la saco para poder probar otra combinacion*/
    t.posiciones[posx][posy] = NULL;
    t.usadas[candidatos[i]->num] = 0;
     t.cant_usadas -= 1;
  }
    
  //Pone un espacio vacio y sigue buscando, pero ya no puede devolver true
  recursion(t,t_opt, piezas, posx, posy+1);
  
  return false;
}

bool backtracking(Tablero &t, vector<Pieza> &piezas)
{ 
  Tablero t_optimo = t;
  //si encuentra una solucion devuelve true
      if(recursion(t,t_optimo, piezas, 0, 0)){return true;}
   
  // si no, t_optimo tiene la optima que utiliza mas piezas
  t=t_optimo;
  return false;
}